226

M. Polychronaki et al.

Fig. 6 The DID standard

• Completeness. An honest verifier should be convinced by the prover if the

statement is true.

• Soundness. An honest verifier should NOT be convinced by the prover if the

statement is false.

• Zero-Knowledge. The verifier has not acquired any further information besides

the fact that the statement is true.

4.1.1

Interactive ZKPs

In order for the verifier to be convinced, a series of interactions between them and the

prover must be conducted. The interaction process is randomized and the verifier tries

to determine whether the prover’s statement is true or not. A very simple example of

an interactive ZKP method is that a prover states that he/she knows the answer to a

sudoku puzzle but does not want to give away the answer to prove it.

The verifier, in order to determine if this statement is true, asks the prover a series

of questions to check the validity of the statement. One question could be to ask the

prover “what is the position of numbers that fill a specific 3 × 3 box in a certain

Sudoku puzzle”. Another question the verifier could use is “How long could it take

for an experienced user to solve a sudoku puzzle of given difficulty”. Figure 6 shows

the abstract interaction between the verifier and the prover in order to be persuaded

about the latter’s honesty.

The correct answer to these questions could persuade the verifier that the statement

of the prover is valid, while the wrong answers could mean that the prover could not

have solved a sudoku puzzle. The more of these questions are answered the higher the

probability of the prover’s honesty. At the same time, in order to avoid the scenario

where the prover and the verifier have preconfigured the questions and answers, the

randomization of these questions should be able to convince a third party for the

statements validity as well (Figs. 7 and 8).

4.1.2

Non-interactive ZKPs

In non-interactive ZKP systems, the prover must shape an argument regarding the

corresponding statement, which anyone can verify its validity. It is to be noted that

non-interactive Zero-Knowledge is a mono-directional process where the prover